package leetCode.function;

import com.alibaba.fastjson.JSON;

// 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
public class MaxRectangleArea {
	
	public static void main(String[] args) {
    	char[][] matrix = {
    			{'1','0','0','0','0','1','0','0','0','0','0'},
    			{'0','0','0','0','0','0','0','0','0','0','0'},
    			{'1','0','0','0','0','1','1','1','0','0','0'},
    			{'1','0','0','0','0','1','1','1','0','0','0'},
    			{'0','0','0','0','0','1','0','1','0','0','0'},
    			{'1','0','0','0','1','1','1','1','1','1','0'},
    			{'0','1','1','1','1','1','1','1','1','1','0'},
    			{'1','1','1','1','1','1','1','1','1','1','0'},
    			{'1','0','0','0','0','1','1','1','0','0','0'},};
    	System.out.println(maximalRectangle(matrix));
    	System.out.println(maximalRectangle1(matrix));
    	System.out.println(maximalRectangle2(matrix));
	}
	
	public static int maximalRectangle2(char[][] matrix) {
		int ret = 0;
		int m = matrix.length;
		if(m == 0) return ret;
		int n = matrix[0].length;
		// 预处理【左侧连续1】的二维数组 或预处理【上侧连续1】的二维数组
		int [][] height = new int[m][n];
		for(int i =0;i<m;i++) {
			for(int j=0;j<n;j++) {
				if(matrix[i][j] == '1') {
					height[i][j] = (i==0?1:height[i-1][j]+1);
				}
			}
		}
		
		for(int i =0;i<m;i++) {
			for(int j=0;j<n;j++) {
				if(height[i][j]==0) continue;
				int minhight = height[i][j];
				if(matrix[i][j] == '1') {
					ret = Math.max(ret, height[i][j]);
					for(int k = j-1;k>=0;k--) {
						if (height[i][k] == 0) {
                            break;
                        }
						minhight = Math.min(minhight, height[i][k]);
						ret = Math.max(ret, minhight*(j-k+1));
					}
					
				}
			}
		}
		return ret;
	}
    
	public static int maximalRectangle1(char[][] matrix) {
		int m = matrix.length;
		if (m == 0)
			return 0;
		int n = matrix[0].length;
		int[][] left = new int[m][n];
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (matrix[i][j] == '1') {
					left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
				}
			}
		}
		int ret = 0;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (matrix[i][j] == '0') {
					continue;
				}
				int width = left[i][j];
				int area = width;
				for (int k = i - 1; k >= 0; k--) {
					width = Math.min(width, left[k][j]);
					area = Math.max(area, (i - k + 1) * width);
				}
				ret = Math.max(ret, area);
			}
		}
		return ret;
	}
    public static int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] heights = new int[rows][cols];
        int maxArea = 0;

        // 计算每个位置上方连续1的个数
        for (int j = 0; j < cols; j++) {
            heights[0][j] = matrix[0][j] - '0';
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == '1') {
                    heights[i][j] = heights[i-1][j] + 1;
                }
            }
        }

        // 对于每个位置作为右下角的矩阵，计算其面积并更新最大面积
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (heights[i][j] > 0) {
                    int width = 1;
                    int minHeight = heights[i][j];
                    maxArea = Math.max(maxArea, minHeight * width);
                    for (int k = j - 1; k >= 0; k--) {
                        if (heights[i][k] == 0) {
                            break;
                        }
                        width++;
                        minHeight = Math.min(minHeight, heights[i][k]);
                        maxArea = Math.max(maxArea, minHeight * width);
                    }
                }
            }
        }

        return maxArea;
    }

}
